package AnswerOfComent;

public class Tencent_53_maxSubArray {
    /**
     * 官方题解
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        int max = nums[0];
        int currMax = 0;
        for (int i = 0; i < nums.length; i++) {
            currMax = Math.max(currMax + nums[i], nums[i]);
            max = Math.max(max, currMax);
        }
        return max;
    }

    /**
     * 大神题解
     * 有一个很巧妙的地方，也是我使用动态规划的时候没考虑到的地方
     * 我在使用动态规划的时候，只会想到当前遍历到的这个数取和不取两种情况。那么出现了一个很不确定的问题：
     *      前一个的取或不取，并不会影响当前这个数取还是不取，于是出现了四种情况了，开始变得很麻烦，而且，所取的数字必须是连续的，所以当前
     *     数值成为单独的一个开始序列之后，就不允许再使用前面的数据进行相加操作了
     */
    public int maxSubArray(int[] nums, boolean noUse) {
        int len = nums.length;
        int[] dp = new int[len];
        dp[0] = nums[0];
        for (int i = 1; i < len; i++) {
            if (dp[i - 1] > 0) {
                dp[i] = dp[i - 1] + nums[i];
            } else {
                dp[i] = nums[i];
            }
        }
        int res = nums[0];
        for (int i = 0; i < len; i++) {
            res = Math.max(res, dp[i]);
        }
        return res;
    }

    /**
     * 大神题解：使用分治法（还不会）
     */
    class Solution {
        public int maxSubArray(int[] nums) {
            if (nums.length == 1) {
                return nums[0];
            }
            return maxSubArraySum(0, nums.length - 1, nums);
        }
        public int maxCrossingSum(int left, int right, int[] nums, int mid) {
            int leftMax = Integer.MIN_VALUE;
            int sum = 0;
            for (int i = mid; i >= left; i--) {
                sum += nums[i];
                if (sum > leftMax) {
                    leftMax = sum;
                }
            }
            sum = 0;
            int rightMax = Integer.MIN_VALUE;
            for (int i = mid + 1; i <= right; i++) {
                sum += nums[i];
                if (sum > rightMax) {
                    rightMax = sum;
                }
            }
            return leftMax + rightMax;
        }

        public int maxSubArraySum(int left, int right, int[] nums) {
            if (left == right) {
                return nums[left];
            }
            int mid = left + (right - left) / 2;
            return max(maxSubArraySum(left, mid, nums), maxSubArraySum(mid + 1, right, nums), maxCrossingSum(left, right, nums, mid));
        }
        public int max(int nums1, int nums2, int nums3) {
            return Math.max(nums1, Math.max(nums2, nums3));
        }
    }
}
